package com.gitee.feizns.explore.data_structure.union_find;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 947. 移除最多的同行或同列石头
 * @author feizns
 * @since 2020/3/12
 */
public class RemoveStones {

    public static void main(String[] args) {
        System.out.println(removeStones(new int[][]{
//                {0, 0},
//                {0, 1},
//                {1, 0},
//                {1, 2},
//                {2, 1},
//                {2, 2}

                //[[1,2],[3,2],[3,0],[4,4],[4,2],[2,4],[4,0]]
                {1, 2},
                {3, 2},
                {3, 0},
                {4, 4},
                {4, 2},
                {2, 4},
                {4, 0}

//                {0, 0},
//                {0, 2},
//                {1, 1},
//                {2, 0},
//                {2, 2}
//                [0,0],[0,2],[1,1],[2,0],[2,2]
        }));
    }

    public static int removeStones(int[][] stones) {
        Uf uf = new Uf(20000);
        for (int i = 0; i < stones.length; i++)
            uf.union(stones[i][0], stones[i][1] + 10000);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < stones.length; i++) {
            set.add(uf.find(stones[i][0]));
            set.add(uf.find(stones[i][1]));
        }
        return stones.length - set.size();
    }

    static class Uf {
        int[] parents;
        int count;
        Uf(int size) {
            parents = new int[size];
            count = size;
            for (int i = 0; i < size; i++)
                parents[i] = i;
        }
        void union(int p, int q) {
            parents[find(p)] = find(q);
        }
        int find(int p) {
            if ( p != parents[p] )
                parents[p] = find(parents[p]);
            return parents[p];
        }
    }

}
